/**
 * @file MergeSort.h
 * @author Crazyfish (wangheyu@zju.edu.cn)
 * @brief A teaching demo for Merge Sort.
 * @version 0.1
 * @date 2020-08-24
 * 
 * @copyright Copyright (c) 2020
 * 
 */

#ifndef __CRAZYFISH_MERGE_SORT__
#define __CRAZYFISH_MERGE_SORT__
#include <vector>
#include <limits>

/**
 * @brief Merge two sorted array parts to a sorted one.
 * 
 * @param _A The object array.
 * @param _p The start index for the first sorted part.
 * @param _q The last index for the first part.
 * @param _r The last index for the second sorted part.
 * @return int Error code. 0 for OK.
 */
int Merge(std::vector<int> &_A, int _p, int _q, int _r);

/**
 * @brief Apply Merge Sort by Divide-and-Conquer strategy.
 * 
 * @param _A The object array. 
 * @param _p The start index to sort.
 * @param _r The last index to sort.
 * @return int Error code. 0 for OK.
 */
int _MergeSort(std::vector<int> &_A, int _p, int _r);

/**
 * @brief A user interface for Merge Sort, just call _MergeSort. 
 * 
 * @param _A The object array.
 * @return int Error code. 0 for OK.
 */
int MergeSort(std::vector<int> &_A);
#else 
// Do nothing.
#endif